ftp.cs.arizona.edu/ftp.cs.arizona.edu.tar/ftp.cs.arizona.edu/tsql/doc/tsql.mail/[e-mail] _Wed Apr 7 17:11:28 1993.msg

Text File | 1996-01-31 | 8KB | 218 lines

Message-Id: <[e-mail]>
Received: from ren.cs.iastate.edu by optima.cs.arizona.edu (5.65c/15) via SMTP
    id AA02681; Wed, 7 Apr 1993 15:11:28 MST
Received: by ren.cs.iastate.edu
    (16.8/16.2) id AA15199; Wed, 7 Apr 93 17:11:28 -0500
From: Shashi K. Gadia <[e-mail]>
Subject: Valid/Transaction time orthogonality
To: [e-mail]
Date: Wed, 7 Apr 93 17:11:28 CDT
Cc: [e-mail]
Mailer: Elm [revision: 70.30]

VALID AND TRANSACTION TIME ORTHOGONALITY.
-----------------------------------------

The following is an on going discussion between
Fabio Grandi and Shashi Gadia about orthogonality
between valid and transaction times in databases.
It may be of general interest.  You are welcome
to participate if you wish.  It is written in a
fairly context free style.
==========================================================

From: Shashi K. Gadia

Dear Fabio:

I am pleased to receive your response.  The orthogonality
between valid and transaction time goes beyond just
(A) Pure valid time, (B) Pure transaction time, and (C) Pure
bitemporal time.  I discuss it in detail below.
   
Diagonal.
---------
I agree that the diagonal in the bitemporal space is
of special interest.  A user having access to the
diagonal sees at once what a classical snpshot user has
seen on a day to day basis.

User.
-----
In our model we introduce concept of a user.  A user is
identified by a subset of the bitemporal space, that the
user is allowed access to.  An application of this concept
of a user is to achieve the orthogonality we are discussing.
Following is an assortment of some interesting users:

A. The system user.
   ----------------
   This user has access to the whole bitemporal space.

B. Audit user.
   -----------
   This is the user who has access to the diagonal (vt=tt)
   and below.  This user sees only present and past.

C. The diagonal user.
   ------------------
   This is the diagonal user we introduced above.

D.  Valid time user.
    -----------------
    The user tt=now.  This user is just like the
    uni-dimensional valid time user.

E.  Classical user.
    ---------------
    {now}x{now}

Other interesting users are possible.  Shortly, we will
introduce another user to solve one of the very interesting
problem you raised.

The set containment leads to a user
lattice hierarchy.  For the purposes of querying, a user
is allowed to set itself equal to any user below it.  This
allows a user to simulate lower users making the hierarchy
quite meaningful.

Now the query "when was John working in Toys" is answered
by every user in the same way:

   [[sigma(emp, NAME=John, [[DEPT=Toys]] ) ]]

   [[retrieve *
     restricted to [[DEPT=Toys]]
     from emp
     where NAME = John]]

THIS INCLUDES THE DIAGONAL USER. This has an interesting
lesson for us.  Why are the English queries looking so
different, syntactically, and even more so semantically,
when something stupid like an algebra is so clean???
This happens all the time in science when new discoveries
are made.  In this case I think the algebra tell us that
we need to integrate new vocabulary into English to
make English cleaner.  In other words, in English we just
ask "when John worked in Toys" without being apologetic
about it.  Let the context (the user that we are) take
care of it.

Our algebra is generic - you apply it to valid time,
transaction time, bitemporal time, no time, even space,
and space and time.  This is the main theme of our chapter
"Temporal databases: a prelude to parametric data"
in the temporal book just published.  The paper coauthored
with Sunil Nair gives SQL which, in our case, is TRIVIALLY
derived from the algebra.  The paper is an exposition
to much of our work.  By the way I also have a chapter
on Ben-zvi's work in the same paper.  This chapter should
be of considerable interest from a historical prospective.


YOUR NEXT QUESTION.
-------------------
When was John's status recorded incorrectly?

(For other readers let me remark that in your case
the salary of an employee is determined from
the status.  So incorrect salary is paid during
the time status is recorded incorrectly in the
database.)

Concept of error can be traced back to Ben-zvi's
bitemporal model (1979-81).  In our bitemporal
model one can query for errors.  The above
query is expressed as follows:

  [[select *
    restrict to [[incorrect value(STATUS)]]
    from emp
    where NAME = John]]

The problem is that it reports more info than you
intended in your message, because you were
only interestsd in errors along the diagonal.
It is important to note that the diagonal user is
rather naive, having no ability to differentiate
between a change and a correction.  To answer the
query in your sense, we need to set ourselves to the
user who can see the diagonal, and the current(ly
known correct version of history) which is stored in
tt = now.  Let us call it Error-user.

Definition: Error-User = diagonal union tt=now.

If we set ourselves to Error-user, the above
query meets your objective.


I like to point out that this work was dome by Gautam
Bhargava and I in 1988-89.  The work includes a bitemporal
model, algebra, sql, capability for querying of errors,
querying updates, querying queries, and achieving zero
information loss in the sense any past interaction with the
database system can be reproduced at any time.

Now some subjective comments.
-----------------------------
In my opinion, the work Bhargava and I did
in 1988-89 makes many things as non issues and makes
certain ideas obsolete.  For example, the concept of
a rollback database is replaced by a transaction time
database, which can be queried as a uni-directional
valid time database.  In the end we must ask: if a user
is willing to store certain amount of history, are
we giving them ability to query whatever is queriable?
Unidimensional transaction time database needs same amount
of storage as a rollback database.  But the transaction time
database allows more comprehensive querying.  This is why
concept of a rollback database is obsolete.

What do we get in going from a unidimensional model to
a bitemporal model?  The answer is a capability to
query for errors.  If we are not giving such a capability
to the user, we are not meeting our promise.

My summary of orthogonality.
----------------------------
What I have seen in the temporal database
literature is handled in a generic manner in
our model.  We can have zero or more dimensions,
some of then can even be spatial.

The orthogonality is broken in in two significant
ways:

1. Updates (I hope this is obvious.)

2. Extraneous information in the bitemporal model.
   -----------------------------------------------
   This aspect needs some explanation.  In a query above
   I used the primitive "incorrect value" and applied
   it to the STATUS attribute to retrieve the
   time domain when the STATUS has been recorded, but
   recorded incorrectly.  Other primitives are "missing
   information", and "extraneous information".  The
   extraneous information is the information about an
   object which exists in the database during the time
   the object does not exist in the real world.

   Extraneous information is the only concept which destroys the
   orthogonality we are discussing.  This is a non-trivial
   idea.  I have not had much success in trying to publish it.
   It has received brutal rejections from one journal, and the
   four most important conferences in databases.  As a result,
   the work has remained dormant.  We have eventually
   published it in a conference proceedings, and now
   in the temporal book.  In my opinion the lack of exposure
   of this work has been the biggest obstacle to progress
   in temporal database.  Perhaps, the problem was that we
   were trying to answer questions people were not asking,
   and not asking even today, five years after the work was
   completed.